package com.love.tree;

/**
 * 堆
 */
public class HeapTree {


    /**
     * 大根堆插入
     * @param arr
     * @param i ： i位置的树，向上调整大根堆
     * arr[i] = x,x是新来的！往上看，直到不必父亲大，或者来的0位置（顶部）
     * i -> 父： （i-2）/2
     */
    public static void heapInsert(int[] arr,int i){
        while (arr[i] > arr[(i - 1) / 2]){
            swap(arr,i,(i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    /**
     * i 位置的数，变小了，又想维持大根堆结构
     * 向下调整大根堆
     * 当前堆的大小为size
     * @param arr
     * @param i
     * @param size
     *    i
     *  左  右
     */
   public static void heapify(int[] arr,int i,int size){
        int l = i * 2 + 1;
        while (l < size){  // 有左孩子
            // 右孩子
            // 评选，最强孩子，是哪个下标的孩子
            int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
            // 上面已经评选了最强的孩子，接下来，当前的数，和最强的孩子之前，最强下标是谁
            best = arr[best] > arr[i] ? best : i;
            if(best == i){
                break;
            }
            swap(arr,best,i);
            i = best;
            l = i * 2 + 1;
        }
   }


    /**
     * 从顶到底建立大根堆
     * 依次弹出堆内最大值并排好队，O( n * logn)
     * 整体的时间复杂度 O(n * logn)
     * @param arr
     */
   public static void heapSort1(int[] arr){
       int n = arr.length;
       for (int i = 0; i < n; i++) {
           heapInsert(arr,i);
       }
       int size = n;
       while (size > 1){
           swap(arr,0,--size);
           heapify(arr,0,size);
       }
   }

    /**
     * 从底到顶建立大根堆，O(n)
     * 依次弹出堆内最大值并排好序，O(n * logn)
     * 整体时间复杂度 O (n * logn)
     * @param arr
     */
   public static void heapSort2(int[] arr){
       int n = arr.length;
       for (int i = n - 1; i >= 0; i--) {
           heapify(arr,i,n);
       }
       int size = n;
       while (size > 1){
           swap(arr,0,--size);
           heapify(arr,0,size);
       }
   }



}
